package com.xmg.dataStructure.tree.redblacktree;

import java.util.Scanner;

/**
 * 红黑树demo
 */
public class RBTreeDemo {
    public static void main(String[] args) {
        RBTree tree = new RBTree();
        Scanner scanner = new Scanner(System.in);
        while (true){
            int val = scanner.nextInt();
//            tree.insert(val);
//            TreeOperation.show(tree.getRoot());
        }
    }
}

class RBTree{
    private static final boolean RED = true;
    private static final boolean BLACK = false;

    private Node root;

    public Node getRoot() {
        return root;
    }

    public Node parentOf(Node node){
        if(node==null){
            return null;
        }else{
            return node.parent;
        }
    }

    public void infixOrder(){
        if(root!=null){
            root.infixOrder();
        }else{
            System.out.println("树为空，无法遍历");
        }
    }

    /**
     *             p               p
     *             |               |
     *             x               y
     *           /  \      ->    /  \
     *         lx    y          x   ry
     *             /  \       / \
     *            ly   ry    lx  ly
     *
     *  1、y的左节点的父节点变为x，x的右子节点变为y
     *  2、当x的父节点不为空时，y的父节点变为x的父节点  并将x的父节点的子树位置（现在x）指向y
     *  3、x的父节点变为y，y的左子节点变为x
     * @param x 以此节点进行左旋
     */
    public void leftRotate(Node x){
        Node y = x.right;
        //1、y的左节点的父节点变为x，x的右子节点变为y
        x.right = y.left;
        if(y.left!=null){
            y.left.parent = x;
        }
        //2、当x的父节点不为空时，y的父节点变为x的父节点  并将x的父节点的子树位置（现在x）指向y
        if(x.parent!=null){
            y.parent = x.parent;
            if(x.parent.left==x){
                x.parent.left = y;
            }else{
                x.parent.right = y;
            }
        }else{
            root = y;
            y.parent=null;
        }
        //3、x的父节点变为y，y的左子节点变为x
        x.parent = y;
        y.left = x;
    }

    /**
     *  1、y的右节点的父节点变为x，x的左子节点变为y
     *  2、当x的父节点不为空时，y的父节点变为x的父节点  并将x的父节点的子树位置（现在x）指向y
     *  3、x的父节点变为y，y的右子节点变为x
     * @param x
     */
    public void rightRotate(Node x){
        Node y = x.left;
        //1
        x.left = y.right;
        if(y.right!=null){
            y.right.parent = x;
        }
        //2
        if(x.parent!=null){
            y.parent = x.parent;
            if(x.parent.left==x){
                x.parent.left = y;
            }else{
                x.parent.right = y;
            }
        }else{
            root = y;
            y.parent=null;
        }
        //3
        x.parent = y;
        y.right = x;
    }

    public void insert(int value){
        Node node = new Node(value);
        node.color = RED;
        insert(node);
    }

    private void insert(Node node){
        Node parent = null;
        Node x = this.root;
        while (x != null){
            parent = x;
            if(node.data<x.data){
                x = x.left;
            }else if(node.data>x.data){
                x = x.right;
            }else{
                x.data = node.data;
                return;
            }
        }
        node.parent = parent;
        if(parent!=null){
            if(node.data<parent.data){
                parent.left = node;
            }else{
                parent.right = node;
            }
        }else{
            root = node;
        }

        insertFixUp(node);
    }

    /**
     * 修复红黑树
     * 修复方法：
     *      |---情景1：红黑树为空树，将根节点染为黑色。
     *      |---情景2：插入节点已经存在，覆盖即可，不需处理。
     *      |---情景3：插入节点的父节点为黑色，插入的节点永远为红色，此时黑色节点没有变化，没有打破平衡，不需要变化
     *
     *      情景4，需要处理
     *      |---情景4：插入节点的父节点为红色
     *          |---情景4.1：叔叔节点存在，并且为红色（叔-父 双红），将爸爸和叔叔染成黑色，将爷爷染成红色，再以爷爷为当前节点进行下一轮
     *          |---情景4.2：叔叔节点不存在或为黑色，父节点为爷爷节点的左子树
     *              |---情景4.2.1：插入节点为其父节点的左子节点（LL情况），将爸爸染成黑色，爷爷染成红色，以爷爷为节点右旋，完成
     *              |---情景4.2.2：插入节点为其父节点的右子节点（LR情况）
     *                             以爸爸节点进行一次左旋，得到4.2.1的LL双红场景，然后制定爸爸为当前节点进行下一轮处理
     *          |---情景4.3：叔叔节点不存在或为黑色，父节点为爷爷节点的右子树
     *              |---情景4.3.1：插入节点为其父节点的右子节点（RR情况），将爸爸染成黑色，爷爷染成红色，以爷爷为节点左旋，完成
     *              |---情景4.3.2：插入节点为其父节点的左子节点（RL情况）
     *                             以爸爸节点进行一次右旋，得到4.2.1的LL双红场景，然后制定爸爸为当前节点进行下一轮处理
     * @param node
     */
    public void insertFixUp(Node node){
        root.color = BLACK;
        Node parent = parentOf(node);
        Node gparent = parentOf(parent);
        if(parent!=null && parent.color==RED){
            //如果存在红色父节点，那么一定存在爷爷节点，因为根节点不能是红色
            Node uncle = null;
            if(parent == gparent.left){
                uncle = gparent.right;
                //情景4.1：叔叔节点存在，并且为红色（叔-父 双红），将爸爸和叔叔染成黑色，将爷爷染成红色，再以爷爷为当前节点进行下一轮
                if(uncle!=null && uncle.color==RED){
                    parent.color = BLACK;
                    uncle.color = BLACK;
                    gparent.color = RED;
                    insertFixUp(gparent);
                    return;
                }
                //叔叔节点不存在或为黑色
                if(uncle==null || uncle.color==BLACK){
                    //情景4.2.1：插入节点为其父节点的左子节点（LL情况），将爸爸染成黑色，爷爷染成红色，以爷爷为节点右旋，完成
                    if(node == parent.left){
                        parent.color = BLACK;
                        gparent.color = RED;
                        rightRotate(gparent);
                        return;
                    }else{
                        //情景4.2.2：插入节点为其父节点的右子节点（LR情况）
                        //           以爸爸节点进行一次左旋，得到4.2.1的LL双红场景，然后指定爸爸为当前节点进行下一轮处理
                        leftRotate(parent);
                        insertFixUp(parent);
                    }
                }
            }else{
                uncle = gparent.left;
                //情景4.1：叔叔节点存在，并且为红色（叔-父 双红），将爸爸和叔叔染成黑色，将爷爷染成红色，再以爷爷为当前节点进行下一轮
                if(uncle!=null && uncle.color==RED){
                    parent.color = BLACK;
                    uncle.color = BLACK;
                    gparent.color = RED;
                    insertFixUp(gparent);
                    return;
                }
                //叔叔节点不存在或为黑色
                if(uncle==null || uncle.color==BLACK){
                    //插入节点为其父节点的右子节点（RR情况），将爸爸染成黑色，爷爷染成红色，以爷爷为节点左旋，完成
                    if(node == parent.right){
                        parent.color = BLACK;
                        gparent.color = RED;
                        leftRotate(gparent);
                    }else{
                        //情景4.3.2：插入节点为其父节点的左子节点（RL情况）
                        //           以爸爸节点进行一次右旋，得到4.2.1的LL双红场景，然后制定爸爸为当前节点进行下一轮处理
                        rightRotate(parent);
                        insertFixUp(parent);
                    }
                }
            }
        }
    }


    static class Node{
        int data;
        boolean color;
        Node left;
        Node right;
        Node parent;

        public Node(int data) {
            this.data = data;
        }

        public void infixOrder(){
            if(this.left!=null) {
                this.left.infixOrder();
            }
            System.out.println(this);
            if(this.right!=null){
                this.right.infixOrder();
            }
        }

        @Override
        public String toString() {
            return "Node{" +
                    "data=" + data +
                    '}';
        }
    }
}
